#!/usr/bin/python
# Filename: Index.py

# Index
# index is used when data records are too large to store in memory
# with index, record can be operated with less disk/external memory read/write
# primary key, secondary key
# index file: with key and reference to record in data file
# sorting index file needs not to change data file
# dense index, spare index(with reference to a group of records)

# Linear Index / Secondary Linear Index
# Multiple-Nodes Tree with overflow area
# ISAM

# Inverted Index:
# for discreted properties(continuous can be dealed with B+/- tree)
# each value of property has a reference to a posting list(a list of reference to records with that property equal to this value)
# when using multiple properties as inverted index, update will cost mush
# Inverted File:
# the reference in posting list is position of document
# stopword, stemming, segmentation
# disadvantage: space cost is usually expensive

# Balanced Tree(B-Tree):
# !!!it's not balanced binary tree
# 1) constructure of rank m B Tree:
# a) each node has at most m children(m-1 keys)
# b) each node has at least upper(m/2) children, except root and leafs
# c) root has at least 2 children, except when root is leaf
# d) all leafs are in the same level
# e) a branch with k children has k-1 keys
# f) every child has a reference to it's parent
# 2) property:
# a) all leafs are in the same level
# b) all keys are different, key of parent is divide of children
# c) store nearby key in a page of external memory, 
# 3) preformance:
# a) search: disk read times <= 1 + log(m/2)((n+1)/2)
# b) insert: divided nodes <= 1/(m/2-1)
# c) nodes in ith level >= 2(m/2)^(i-1)
# c.1) complete k-tree theorem: external nodes = (k-1)nodes + 1
# c.2) in balanced tree, k-1 is just keys in branch, so n + 1 = external nodes(assuming in level i) >= 2(m/2)^(i-1)
# c.3) i <= 1 + log(m/2)((n+1)/2)
# c.4) tree level should be i-1 bcz i is level of external nodes, but i starts from 0, so i is time of disk read
# 4) it's very special that root can have only 2 children, that's result of division
# 5) delete algorithm:
# a) switch key to be deleted to leaf
# b) delete
# c) borrow or merge(if remaining keys < m/2-1)
# d) parent rebuild(if remaining keys in parent < m/2-1 after children merge)

# B+ Tree:
# all keys store in leaves
# keys in branch is a copy of it's children's greatest/least key
# constructure of rank m B+ Tree:
# a) b) c) d)
# e) a branch with k children has k keys

# VSAM


class BalanceTreeNode:
    pass

class BalanceTree:
    pass
